/*
 * bin_search_tree.c
 *
 *  Created on: 2020��1��8��
 *      Author: Administrator
 */

#include <stdio.h>
#include <stdlib.h>
#include "../../include/tree/bin_search_tree.h"
#include "../../include/tree/binary_tree.h"

BSTree* create_bst(int array[], int length) {

	BSTree* tree = NULL;
	for (int i = 0; i < length; ++i) {
		tree = insert_btnode(tree, array[i]);
	}
	return tree;
}

bool is_bst_empty(BSTree* root) {

	if (root == NULL)
		return true;
	return false;
}

BSTree* insert_btnode(BSTree* root, int value) {

	// ���Ϊ����
	if (root == NULL) {
		BTNode* node = (BTNode*) malloc(sizeof(BTNode));
		node->data = value;
		node->left = node->right = NULL;
		root = node;
	} else if (root->data > value) {
		root->left = insert_btnode(root->left, value);
	} else { // tree->data < value
		root->right = insert_btnode(root->right, value);
	}
	return root;
}

int get_bst_nodes(BSTree* root) {

	int count = 0;
	if (root == NULL) {
		return 0;
	} else {
		count = get_bst_nodes(root->left) + get_bst_nodes(root->right) + 1;
		return count;
	}
}

void preorder_bst(BSTree* root) {

	if (root == NULL) {
		return;
	} else {
		printf("%d ", root->data);
		preorder_bst(root->left);
		preorder_bst(root->right);
	}
}

void inorder_bst(BSTree* root) {

	if (root == NULL) {
		return;
	} else {
		inorder_bst(root->left);
		printf("%d ", root->data);
		inorder_bst(root->right);
	}
}

BTNode* search_bst(BSTree* root, ElemType key) {

	if (root == NULL)
		return NULL;

	if ((ElemType) root->data == key)
		return root;
	else if (root->data > key)
		return search_bst(root->left, key);
	else
		return search_bst(root->right, key);
}

BTNode* unr_search_bst(BSTree* root, ElemType key) {

	BTNode* p = root;
	while (p) {
		if (p->data == key)
			return p;
		else if (p->data > key)
			p = p->left;
		else
			p = p->right;
	}
	return p;
}

void delete_bst(BSTree* root, ElemType key) {

	BTNode *p, *f, *s, *q;
	p = root; // p指向待删结点
	f = NULL; // f为p结点的双亲结点
	// 查找关键字k
	while (p) {
		if (p->data == key)
			break;
		f = p;
		if (p->data > key)
			p = p->left;
		else
			p = p->right;
	}
	// 若找不到，则返回
	if (p == NULL) return;

	// 如果待删除结点p左右子树均存在，使用前驱代替待删除结点
	if (p->left && p->right) {
		q = p;       // q为前驱s的父亲
		s = p->left; // s为待删除结点p的前驱

		while (s->right) {
			q = s;
			s = s->right;
		}
		p->data = s->data;  // 前驱s代替待删除结点p

		if (q != p) {
			q->right = s->left; // 重接q的右子树
		} else {
			q->left = s->left;  // 重接q的左子树
		}
		free(s);

	} else {
		// p右子树为空
		if (p->right == NULL) {
			q = p->left;   // q指向左子树
		} else if (p->left == NULL) {
			q = p->right;  // q指向右子树
		}
		// 将p的子树挂接到待删除结点双亲f的相应位置
		if (f == NULL)
			root = q;
		else if (f->left == p)
			f->left = q;
		else if (f->right == p)
			f->right = q;
		free(p);
	}
}
